ABC170 E
20万個の数値が20万個の集合を20万回動き回る。
このとき「集合の最大値」の最小値を各移動ごとに求めよ、という問題。 コンテスト中の思考
当然、各移動ごとに各集合に対してO(N)の処理をしたらTLEするだろう。
かな？
しかし数の移動に伴って、「最大値の集合」から最小値以外の値が取り除かれることがある。例: {1}, {2}, {3} → {1}, {2, 3}, {}
うーん、ソート済みの配列に対する二分探索で目的のものを見つけて…いや配列への追加削除がO(N)だから追加削除を繰り返す攻撃でTLEにされるな。
リンクトリストにすることで追加削除のコストを下げる…いや、それだと削除対象を見つけるのがO(N)じゃん…じゃあ双方向リストにして、かつ各オブジェクトへのインデックスをつける？？？？
などの意見が…なるほど追加削除O(N)をO(1)にしようとして「あちらを立てればこちらが立たず」だったが、全般的にO(logN)にすれば良いのか。方向性はわかった。
それで具体的な実装はどうするのかな…あれ？heapqを使ってる人がいるぞ？
なるほど。ヒープキューの先頭以外の要素を取り除くコストは高いが、取り除かなければ良い、その代わり読み飛ばす仕組みをつければ良い、と。
集合から離れた人は先頭以外の場合は取り除かない
先頭の人が取り除かれた場合の次の人を探すタイミングで「同じ人」と「現時点で他の集合に入ってる人」を取り除く
「集合ごとの最大スコアのヒープキュー」も更新時に古い要素を取り除かない
代わりに各集合ごとに「自分が最後に最大スコアを更新した時刻」を記録する
出力のために先頭要素を取得した時点で、それが古いデータであれば捨てる
というわけで参考にしつつ書いたコードはACになった
感想
これでTLEしないということに確信が持てない…
適当なAVL木の実装を持ってきて置き換えてみた
→コードはシンプルになるが、TLE
オーダーはO(logN)のはずだが定数倍が大きい？
PyPy実装の人の速い方から5件をみる
個別の集合を持つのには4人がheapq。数が多いのでツリー構築はオーバーヘッドが大きいから避けられてるのだろう。削除をする代わりに読み飛ばすアプローチは広く使われてるようだ。一人だけset、つまりハッシュマップ的アプローチでやってる人がいた。意外な抜け道。
最大値の集合を持つのには、セグメント木3人、heapq1人、フェニック木1人。フェニック木も面白そうだけど、とりあえずセグメント木が使えるようになりたいなーという気持ちになった。 二つのheapqで集合に入った数値と抜けた数値を保管
セグメント木で最小値を求める
シフトを使ってるのはタプルを使わずに数値をパックするため
heapqに入れる、離れた人を先頭取得時に取り除く
最大値の集合もheapqに入れる
最小値の人が、最小値の人の所属する集合の最大値でないなら読み飛ばす
それでいいのか？？
heapqに入れる、離れた人を先頭取得時に取り除く
移動元と移動先の最大値をセグメント木に入れる
この人のセグメント木のコードは読みやすい
集合を集合(set)で表現
集合の最大値は普通にmaxで計算
それでTLEならないのか？
単純に真似したら一つの集合に密集してるhandmade06などのテストケースでTLEになった
よく読むとうまい工夫があるのかもしれない
他のheapqアプローチが(レート, 人ID)の対を入れてるのに対してこちらはレートだけを入れてるのが独特
最大値はセグメント木に入れる
集合はheapqで表現
最大値の集合はBinary Indexed Tree(フェニック木) 更新が効率的に行える
座標圧縮は木のサイズを小さくするのに寄与する
これを踏まえて